package point;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 题目：在连续的正数序列中找到 和 等于目标值的 连续序列
 * 例子：和等于15的连续序列为：
 * [1, 2, 3, 4, 5]
 * [4, 5, 6]
 * [7, 8]
 *
 * 思路：使用双指针，连续正数指针可以可以先从1 和 2 开始（最小sum为3），临界点为 RP 等于target。
 * 如果curSum > target, curSum减去旧指针,LP移动1。
 * 如果curSum < target, RP移动1，curSum加上新的指针。
 * 如果相等，把本次结果放到List中，然后整体后移继续运算，因为其他移动都是不合理的。（LP - 1 > target; RP - 1 < target; LP - 1 & RP + 1 > target;  LP + 1 & RP - 1 < target;>）
 */

public class FindContinuousSum {

    public static void main(String[] args) {
        FindContinuousSum findContinuousSum = new FindContinuousSum();
        List<List<Integer>> res = findContinuousSum.findContinuousSum(15);
        for (List<Integer> list : res) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }

    public List<List<Integer>> findContinuousSum(int target) {
        List<List<Integer>> res = new ArrayList<>();
        int left = 1, right = 2;
        int curSum = 3;
        while (right < target) {
            if (curSum > target) {
                curSum -= left;
                left++;
            } else if (curSum < target) {
                right++;
                curSum += right;
            } else {
                List<Integer> numList = new ArrayList<>();
                for (int i = left; i <= right; i++) {
                    numList.add(i);
                }
                res.add(numList);
                curSum -= left;
                right++;
                left++;
                curSum += right;
            }
        }
        return res;
    }
}
